package leetcode101_xqzhao

// TODO 最大子数组和 【-】 动态规划

func maxSubArray(nums []int) int {
	n := len(nums)
	dp := make([]int, n)
	dp[0] = nums[0]

	// 状态转移
	for i := 1; i < n; i++ {
		dp[i] = max1(dp[i-1]+nums[i], nums[i])
	}

	maxSum := dp[0]
	for i := 0; i < n; i++ {
		maxSum = max1(maxSum, dp[i])
	}

	return maxSum
}

func max1(a int, b int) int {
	if a > b {
		return a
	}
	return b
}
